//字符串相乘
//测试链接 https://leetcode.cn/problems/multiply-strings/
public class Multiply {
    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0") ) return "0";

        int n1 = num1.length(), n2 = num2.length();
        int len = n1 + n2 - 1;
        int[] mul = new int[len];

        //翻转两个字符串
        num1 = new StringBuilder(num1).reverse().toString();
        num2 = new StringBuilder(num2).reverse().toString();
        for(int i = 0; i < n2; i++) {
            for(int j = 0; j < n1; j++) {
                int num =( num2.charAt(i) - '0' ) * ( num1.charAt(j) - '0' );
                int index = i + j;
                mul[index] += num;
            }
        }
        StringBuilder ret = new StringBuilder();
        int sum = 0; //表示进值
        int cur = 0;
        while(cur < len || sum != 0) {
            int num = 0;
            if(cur < len ) num = mul[cur++];
            sum += num;

            ret.append((char) ((sum%10) + '0') );
            sum /= 10;
        }
        //处理前导0
        while(ret.length() > 1 && ret.charAt(ret.length()-1) == '0'){
            ret.deleteCharAt(ret.length()-1);
        }

        return ret.reverse().toString();
    }
}
